package Leetcode.lc028;

/***
 * KMP算法
 */
public class Sloution {

    public void getNext(int[] nums,String moudle){
        /***
         * 本质上是一种主串不回退，模式串回退的匹配算法
         * 本来也有双指针，本质上是一种双指针
         */
        int j=0;
        nums[j]=0;
        /***
         * 设有一数组 abcdaaq
         * 第一个必定为0，故从1开始,所以回溯的地方排除为0
         */
        for(int i=1;i<moudle.length();i++){
            while (j>0 && moudle.charAt(i)!=moudle.charAt(j)){
                j=nums[j-1];
            }
            /***
             * 若前后最相等
             */
            if(moudle.charAt(i)==moudle.charAt(j)) j++;
            nums[i]=j;
        }
    }

    /***
     *
     * @param haystack 匹配串
     * @param needle 模式串
     * @return 返回匹配的首位下标
     */
    public int strStr(String haystack, String needle) {
        int len=0;
        int[] next=new int[needle.length()];
        getNext(next,needle);
        for(int i=0;i<haystack.length();i++){
            //处理特殊情况
            while(len>0 && haystack.charAt(i)!=needle.charAt(len)){
                len=next[len-1];
            }
            //相等的情况
            if(haystack.charAt(i)==needle.charAt(len)){
                len++;
            }
            if(len==needle.length()){
                return i-needle.length()+1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Sloution sloution = new Sloution();
        String a="aabbccdd";
        String b="ab";
        int res=sloution.strStr(a,b);
        System.out.print(res);
    }
}
